#include <stdlib.h>
#include <time.h>
#include <stdio.h>

#define ARRAY_SIZE 10
#define NUMBER_RANGE 1000

typedef struct Node{
	int data;
	struct Node *next;
} Node,*PNode;

void insertion_sort_list(PNode head){
	PNode p = NULL;
	PNode q = NULL;
	PNode t = NULL;
	int data = -1;
 	if(head->next!=NULL){
		p = head->next;
		while(p!=NULL){
			data = p->data;
			q = p->next;
			if(q!=NULL&&q->data<data){
				p->next = q->next;
				t = head;
				while(t->next->data<=q->data){
					t=t->next;
				}
				q->next = t->next;
				t->next = q;
			}
			p = p->next;
		}
	}
}

void bucket_sort(int arr[],int len,int range){
	int count = 10; 
	int size = range/count;
	PNode bucket = (PNode)malloc(size*sizeof(Node));
	int i = 0;
	for(i=0;i<count;i++){
		bucket[i].data = -1;
		bucket[i].next = NULL;
	}
	PNode temp=NULL;
	PNode p = NULL;
	for(i=1;i<=len;i++){
		temp = bucket+arr[i]/size;
		while(temp->next!=NULL){
			temp = temp->next;
		}
		p = (PNode)malloc(sizeof(Node));
		p->data = arr[i];
		p->next = NULL;
		temp->next = p;
	}
	
	for(i=0;i<count;i++){
		insertion_sort_list(bucket+i);
	}

	int j=0;
	i=1;
	for(j=0;j<count;j++){
		p = bucket+j;
		temp = p;
		p = p->next;
		free(temp);
		while(p!=NULL){
			arr[i++] = p->data;
			temp = p->next;
			free(p);
			p = temp;
		}
		
	}
	
}


int main(){
    int i = 0;
    int arr[ARRAY_SIZE+1];
    int ret[ARRAY_SIZE+1];

    srand((unsigned)time(NULL));
    for(i=1;i<=ARRAY_SIZE;i++){
        arr[i] = rand()%NUMBER_RANGE;
    }

    printf("sort array  [");
    for(i=1;i<=ARRAY_SIZE;i++){
        printf("%d",arr[i]);
        if(i<ARRAY_SIZE){
            printf(",");
        }
    }
    printf("] \n");
    bucket_sort(arr,ARRAY_SIZE,NUMBER_RANGE);

    printf("sort result [");
    for(i=1;i<=ARRAY_SIZE;i++){
        printf("%d",arr[i]);
        if(i<ARRAY_SIZE){
            printf(",");
        }
    }
    printf("] \n");

    return 0;
}

